package com.fyl.leetcode.sort;

import java.util.Arrays;
import java.util.PriorityQueue;

/**
 * @author:fyl
 * @date 2021/4/26 17:38
 * @Modified By:
 * @Modified Date:
 * @Description: 在未排序的数组中找到第 k 个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
 * 示例 1:
 * 输入: [3,2,1,5,6,4] 和 k = 2
 * 输出: 5
 * 用于求解 TopK Elements 问题，也就是 K 个最小元素的问题。
 * 使用最小堆来实现 TopK 问题，最小堆使用大顶堆来实现，大顶堆的堆顶元素为当前堆的最大元素。
 * 实现过程：不断地往大顶堆中插入新元素，当堆中元素的数量大于 k 时，移除堆顶元素，也就是当前堆中最大的元素，剩下的元素都为当前添加过的元素中最小的 K 个元素。
 * 插入和移除堆顶元素的时间复杂度都为 log2N。
 *
 * 堆也可以用于求解 Kth Element 问题，得到了大小为 K 的最小堆之后，因为使用了大顶堆来实现，因此堆顶元素就是第 K 大的元素。
 *
 * 快速选择也可以求解 TopK Elements 问题，因为找到 Kth Element 之后，再遍历一次数组，所有小于等于 Kth Element 的元素都是 TopK Elements。
 */
public class KthElement {
    public int findKthLargest(int[] nums, int k) {
        PriorityQueue<Integer> queue = new PriorityQueue<>();
        for (int num : nums) {
            queue.add(num);
            if (queue.size() > k) {
                queue.poll();
            }
        }
        return queue.peek();
    }

    public int findKthLargest2(int[] nums, int k) {
        k = nums.length - k;
        int left = 0;
        int right = nums.length - 1;
        while (left < right) {
            int q = partition(nums, left, right);
            if (q == k) {
                break;
            } else if (q < k) {
                left = q + 1;
            } else {
                right = q - 1;
            }
        }
        return nums[k];
    }

    private int partition(int[] array, int left, int right) {
        int pivot = array[right];
        int i = left;
        for (int j = left; j < right; j++) {
            if (array[j] < pivot) {
                if (i == j) {
                    i++;
                } else {
                    int temp = array[i];
                    array[i++] = array[j];
                    array[j] = temp;
                }
            }
        }

        int temp = array[i];
        array[i] = pivot;
        array[right] = temp;

        return i;
    }
}
